/**
 * @author: shiding
 * @data: 2022/5/25 19:55
 **/
public class MiddleNode {

    public static void main(String[] args) {
        ListNode list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode node = middleNode1(list);
        System.out.println("中间节点：" + node.val);
    }

    /**
     * 暴力解法：
     * 1、遍历链表 获取链链表长度
     * 2、middIndex = length / 2
     * 3、再次遍历获取 中间位的链表节点
     * @param list
     * @return
     */
    public static ListNode middleNode(ListNode list) {
        ListNode temp = list;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        if (length == 1) {
            return list;
        }
        int middleIndex = length / 2;
        while (middleIndex != 0) {
            middleIndex--;
            list = list.next;
        }
        return list;
    }

    /**
     * 暴力解法：
     * 使用快慢指针： 面对链表 恒定的往同一个方向前进 快指针 走到 最后时，慢指针会在中间
     * slow 走一步
     * fast 走两步
     * @param list
     * @return
     */
    public static ListNode middleNode1(ListNode list) {
        // 快慢指针初始化指向 head
        ListNode slow = list, fast = list;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}


